|
|
Minimum 0-Extensions of Graph Metrics
Dvořák, Martin ; Bulín, Jakub (vedoucí práce) ; Majerech, Vladan (oponent)
Uvažujeme Minimum 0-Extension problém pro pevně-daný neori- entovaný graf s kladnými vahami hran. Studujeme výpočetní složitost jeho rozhodovací varianty v závislosti na vlastnostech toho pevně-daného grafu, konkrétně s ohledem na to, zda je tento graf modulární a zda je orientovatelný ve smyslu, jak ho definoval Karzanov [Eur. J. Comb., 19/1 (1998)]. Na tento problém se díváme z pohledu Finite-Valued CSP, což nám umožňuje využít bohatství teorie, která byla vyvinuta pro důkaz jejich dichotomie. V rámci spodního odhadu složitosti, nejprve zkonstruujeme explicitní re- dukci z Max-Cut problému, čímž získáme NP-těžkost pro nemodulární grafy. Pro neorientovatelné grafy vyjádříme funkci, která splní určitou podmínku, jež zaručí existenci implicitní redukce z Max-Cut problému. Co se týče pozi- tivních výsledků, pomocí symetrických zlomkových polymorfismů ukážeme, že některé speciální případy pro vážené modulární orientovatelné grafy lze řešit technikou zvanou Basic LP Relaxation, konkrétně Minimum 0-Extension problém pro grafy typu cesta a pro grafy typu obdélník. 1
|
host ::
RSS.